package com.xiaojianhx.demo.algorithm.sort;

import com.xiaojianhx.demo.algorithm.utils.Utils;

/**
 * 希尔排序
 * 
 * @author xiaojianhx
 * @version V1.0.0 $ 2021-08-06 13:50:09 init ---- xiaojianhx
 */
public class Algorithm_Sort_06_ShellSort {

    /** 交换法 */
    public static void sort(int[] arr) {

        // 增量gap，并逐步缩小增量
        for (var gap = arr.length / 2; gap > 0; gap /= 2) {

            // 从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (var i = gap; i < arr.length; i++) {

                var j = i;

                while (j - gap >= 0 && arr[j] < arr[j - gap]) {
                    Utils.swap(arr, j, j - gap);
                    j -= gap;
                }
            }
        }
    }

    /** 移动法 */
    public static void sort1(int[] arr) {

        // 增量gap，并逐步缩小增量
        for (var gap = arr.length / 2; gap > 0; gap /= 2) {

            // 从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (var i = gap; i < arr.length; i++) {

                var j = i;
                int temp = arr[j];

                if (arr[j] < arr[j - gap]) {

                    while (j - gap >= 0 && temp < arr[j - gap]) {

                        // 移动法
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }

                    arr[j] = temp;
                }
            }
        }
    }
}